package B刷题.前缀树;

import java.util.HashMap;

/**
 * @author wei.zhao
 * @description: 剑指 Offer II 062.实现前缀树
 * @date 2022年11月17日 15:36
 */
public class Trie {

    public int pass;

    public int end;

    public HashMap<Character, Trie> nexts;

    /**
     * Initialize your data structure here.
     */
    public Trie() {
        pass = 0;
        end = 0;
        nexts = new HashMap<>();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        this.pass++;
        if (word == null || word == "") {
            this.end++;
            return;
        }
        char[] chars = word.toCharArray();
        Trie now = this;
        for (int i = 0; i < chars.length; i++) {
            char aChar = chars[i];
            if (now.nexts.get(aChar) == null) {
                now.nexts.put(aChar, new Trie());
            }
            Trie trie = now.nexts.get(aChar);
            trie.pass++;
            if (i == chars.length - 1) {
                trie.end++;
            }
            now = trie;
        }
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        if (word == null || word == "") {
            return this.end != 0;
        }
        char[] chars = word.toCharArray();
        Trie now = this;
        for (int i = 0; i < chars.length; i++) {
            char aChar = chars[i];
            Trie trie = now.nexts.get(aChar);
            if (trie == null) {
                return false;
            }
            if (i == chars.length - 1) {
                return trie.end != 0;
            }
            now = trie;
        }
        return false;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        if (prefix == null || prefix == "") {
            return this.end == 0;
        }
        char[] chars = prefix.toCharArray();
        Trie now = this;
        for (int i = 0; i < chars.length; i++) {
            char aChar = chars[i];
            Trie trie = now.nexts.get(aChar);
            if (trie == null) {
                return false;
            }
            now = trie;
        }
        return true;
    }

}
